#include <iostream>
#include <iterator>
#include <algorithm>

int binary_search(int a[], int n, int key){
	int left = 0;
	int right = n-1;
	while(left <= right) {
		int mid = (left+right)/2;
		if(key == a[mid]) 
			return mid;
		else if(key < a[mid])
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}

int bsearch(int a[], int left, int right, int key) {
	if (left>right)
		return -1;
	int mid = (left+right)/2;
	if (key == a[mid])
		return mid;
	else if (key < a[mid])
		return bsearch(a, left, mid-1, key);
	else
		return bsearch(a, mid+1, right, key);
}

int bsearch_tail_recursion(int a[], int left, int right, int key) {
	if (left>right)
		return -1;
	int mid = (left+right)/2;
	if (key == a[mid])
		return mid;
	else if (key < a[mid])
		right = mid - 1;
	else
		left = mid + 1;
	return bsearch_tail_recursion(a, left, right, key);
}

int bsearch_iterative_0(int a[], int left, int right, int key) {
	while(true){
		if (left>right)
			return -1;
		int mid = (left+right)/2;
		if (key == a[mid])
			return mid;
		else if (key < a[mid])
			right = mid - 1;
		else
			left = mid + 1;
	}
}

int bsearch_iterative_1(int a[], int left, int right, int key) {
	while(left <= right){			
		int mid = (left+right)/2;
		if (key == a[mid])
			return mid;
		else if (key < a[mid])
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}
void test_bsearch(){
	int a[] = {1, 3, 5, 7, 9, 11, 13};
	int n = sizeof(a)/sizeof(int);
	int key;
	std::copy(a, a+n, std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl;
	while(std::cin >> key) {
		int index = bsearch(a, 0, n-1, key);
		std::cout << (index>=0 ? "found " : "not found ") << index << std::endl;

		index = bsearch_tail_recursion(a, 0, n-1, key);
		std::cout << (index>=0 ? "found " : "not found ") << index << std::endl;

		index = bsearch_iterative_0(a, 0, n-1, key);
		std::cout << (index>=0 ? "found " : "not found ") << index << std::endl;

		index = bsearch_iterative_1(a, 0, n-1, key);
		std::cout << (index>=0 ? "found " : "not found ") << index << std::endl;
	}
}